package com.hs;

/**
 * @Author: hs
 * @Description:
 * @Date: Create in 10:06 2019/3/7
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = {12, 1, 3, 7, 34, 56, 34, 12,  -3,3,-23,76, 9};
        quickSort(0,arr.length-1,arr);
        printArr(arr);
    }

    /**
     * 快速排序
     * 快速排序优点是快，有个确定就是不稳定（相同值的原始顺序可能会变化）
     * @param left  左下标
     * @param right 右下标
     * @param arr   数组
     */
    public static void quickSort(int left, int right, int[] arr) {
        // 左下标
        int l = left;
        // 右下标
        int r = right;
        // 以中间的值为基准进行分割,取哪个做为中间值不影响最后的结果，所以不要在意中间值的下标。
        int pivot = arr[(left + right) / 2];
        //int pivot = arr[right];
        int temp;

        // while 语句的作用就是把比 pivot 小的数放到左边, 比 pivot 大的数放到右边
        while (l < r) {
            //从左边找一个比 pivot 大(或等于)的值对应下标（等于也必须调整）
            while (arr[l] < pivot) {
                l += 1;
            }
            //从右边找一个比 pivot 小(或等于)的值对应下标
            while (arr[r] > pivot) {
                r -= 1;
            }
            // 说明本次交换结束,退出本次 while
            if (l >= r) {
                break;
            }
            //交换
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            //处理后，如果发现 arr(l) == pivot 就 r - =1 , 是避免 相等的数据不断调换，造成死循环，顺便提高一点点效率
            if (arr[l] == pivot) {
                r -= 1;
            }
            //处理后，如果发现 arr(r) == pivot 就 l - =1,是避免 相等的数据不断调换，造成死循环，顺便提高一点点效率
            if ((arr[r]) == pivot) {
                l += 1;
            }
        }
        //printArr(arr);
        // 提高效率 避免死循环
        if (l == r) {
            l += 1;
            r -= 1;
        }
        //向左递归排序
        if (left < r) {
            quickSort(left, r, arr);
        }
        //向右递归排序
        if (right > l) {
            quickSort(l, right, arr);
        }
    }


    public static void printArr(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if (arr.length - 1 != i) {
                System.out.print(",");
            }
        }
    }
}
